package top100;

/**
 * @author Godc
 * @description
 */
public class FindMedianSortedArrays {
    public static void main(String[] args) {

        FindMedianSortedArraysSolution s = new FindMedianSortedArraysSolution();
//        s.findMedianSortedArrays(new int[]{1,2},new int[]{3,4});


    }
}
class FindMedianSortedArraysSolution {
    /**
     * 第一种思路是先利用归并排序的归并，然后找中位数，时间复杂度o(m+n)不符合要求
     * 所以本题采用寻找第K大数字的思路
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 为了简化代码，不分情况讨论，我们使用一个小trick，我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，
        // 然后求其平均值即可，这对奇偶数均适用。加入 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，
        // 相当于两个相同的数字相加再除以2，还是其本身。
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    public int findKth(int nums1[],int i,int nums2[],int j,int k){
        // 如果有一方指针已经超过了数组长度，说明整个数组的数字都被淘汰了，再另一个数组中找第k大就行
        if(i>=nums1.length) return nums2[j+k-1];
        if(j>=nums2.length) return nums1[i+k-1];
        // 找排序第一的较小的数组
        if(k==1) return Math.min(nums1[i],nums2[j]);
        // 再两个数组中各找第k/2大的数字进行比较
        // 如果第一个数组的第K/2个数字小的话，那么说明我们要找的数字肯定不在nums1中的前K/2个数字，所以我们可以将其淘汰，
        // 将nums1的起始位置向后移动K/2个，并且此时的K也自减去K/2，调用递归。反之，我们淘汰nums2中的前K/2个数字，并将nums2的起始位置向后移动K/2个，
        // 并且此时的K也自减去K/2，调用递归即可。
        int midVal1 = (i+k/2-1<nums1.length)?nums1[i+k/2-1]:Integer.MAX_VALUE;
        int midVal2 = (j+k/2-1<nums2.length)?nums2[j+k/2-1]:Integer.MAX_VALUE;
        if(midVal1 < midVal2){
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }
    }
}
